package com.modernyuanshiren;

import java.util.Collections;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;

public class PermSupplier<T extends Comparable<T>> implements Supplier<List<T>> {
    private boolean isInit;
    private final List<T> result;

    public PermSupplier(List<T> init) {
        isInit = true;
        result = init;
        Collections.sort(result);
    }

    @Override
    public List<T> get() {
        if (isInit) {
            isInit = false;
            return result.stream().collect(Collectors.toList());
        }
        if (nextNumber()) {
            return result.stream().collect(Collectors.toList());
        }
        throw new RuntimeException("完了");
    }

    private boolean lessThan(int idx1, int idx2, Boolean... canEqual) {
        if (canEqual.length == 0 || !canEqual[0]) {
            return result.get(idx1).compareTo(result.get(idx2)) < 0;
        }
        return result.get(idx1).compareTo(result.get(idx2)) <= 0;
    }

    private boolean nextNumber()
    {
        // 从右向左确定第一个数字（前面的数字比它小）
        int lastIndex = result.size() - 1;
        int firstIndex = lastIndex;
        for (; !lessThan(firstIndex - 1, firstIndex); firstIndex--)
        {
            if (firstIndex == 1)
            {
                // 已经轮询完毕,此数已经是最大的那个数
                return false;
            }
        }
        // 从右向左确定一个交换数（此数比arr[firstIndex]小且比arr[firstIndex-1]大）
        int swapIndex = lastIndex;
        for (; swapIndex > firstIndex; swapIndex--)
        {
            if (lessThan(swapIndex, firstIndex, true) && lessThan(firstIndex - 1, swapIndex))
            {
                break;
            }
        }
        Collections.swap(result, firstIndex - 1, swapIndex);
        // 将firstIndex右边的数字排序
        for (; firstIndex < lastIndex; firstIndex++, lastIndex--)
        {
            if (lessThan(lastIndex, firstIndex))
            {
                Collections.swap(result, firstIndex, lastIndex);
            }
        }
        return true;
    }

}
